The least recently used (LRU) algorithm is typically the way that conflict for the use of a group of elements is resolved. That is, when all of a group of elements are occupied and a further demand for use of one of these elements is made, it is necessary to change the current dedication of one of these elements, and instead devote it to the new demands made on the group. The LRU algorithm specifies that in situations like this the element which has been unused for the longest time is the one to be devoted to this new use.
This situation arises most frequently in competing demands for various areas of a memory, each area essentially comprising a single element. Information is stored in an area for use by a processor. After all the elements contain current and useful information, a need for further information not contained in any of the elements cannot to be honored without replacing information currently held in one area or element with the information newly required. In this situation, the LRU algorithm simply specifies that the element which contains the information which was last used earliest in time relative to the information in the other elements, should be the information which is overwritten and destroyed. To accomplish this effectively, a memory must be used to record temporarily each use of an element's information. Typically, this has been done in the past simply by using individual memory flip-flops which receive signals indicating the use of a particular element and which change state when the later use of an element relevant to another element changes. This is shown for example, in our previous patent application entitled "Degradable LRU Circuit," Ser. No. 06/200,876, filed Oct. 27, 1980, now U.S. Pat. No. 4,361,878, and having a common assignee with this application.
In typical memory applications required now, there may be two or more sets of memory, each of which can be referenced separately. Each set is in turn subdivided into a number of areas or elements. It is desired to resolve the LRU status between a group of associated elements, one element in each group provided by each memory set. The use of a series of groups of flip-flops, where a single group of flip-flops is associated with each group of elements and receives the use signals from them is a clumsy and impractical solution to this requirement. Accordingly, there is substantial motivation to implement this function in a more efficient manner.